package com.algorithms.leetcode.Arrays;

import java.util.Arrays;

/**
 *给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * https://leetcode-cn.com/problems/move-zeroes/
 * <br>
 */
public class leetcode_283_moveZeroes {
    /**
     *  1.申请一个临时数组
     *  2.将不为0的数放到临时数组前面
     *  3.将临时数组的值复制回nums
     *  时间复杂度： O(n) + O(n) =  O(n);
     *  空间复杂度： O(n)
     * @param nums
     */
    public static void moveZeroesV1(int[] nums) {
       if(nums == null || nums.length == 0){
           return ;
       }
       int[] tmp = new int[nums.length];
       int j = 0;
       for(int i = 0;i < nums.length;i++){
           if(nums[i] != 0){
               tmp[j++] = nums[i];
           }
       }
       for(int i = 0;i < nums.length;i++){
           nums[i] = tmp[i];
       }
    }

    /**
     * 双指针优化空间(快慢指针)
     * 原地算法
     *  时间复杂度： O(n);
     *  空间复杂度： O(1)
     */
    public static void moveZeroesV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int slow = 0;
        for(int fast = 0;fast < nums.length;fast++){
            if(nums[fast] != 0){
                if(slow != fast){
                    int tmp = nums[slow];
                    nums[slow] = nums[fast];
                    nums[fast] = tmp;
                }
                slow++;
            }
        }
    }

    /**
     * 另一个参考
     * @param nums
     */
    public static void moveZeroesV3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != 0) {
                if (slow != fast) {
                    // 减少赋值的次数
                    nums[slow] = nums[fast];
                }
                slow++;
            }
        }
        //后面的元素补0
        for (; slow < nums.length; slow++) {
            nums[slow] = 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,3,12};
        moveZeroesV2(nums);
        System.out.println(Arrays.toString(nums));
    }
}
